The remainder from a Galois field polynomial division is useful for purposes such as encoding data for block error correcting codes, including Reed Solomon codes. Polynomial division is the division of a dividend polynomial by a divisor polynomial. The result of a polynomial division is a quotient polynomial and a remainder polynomial. A polynomial is a sum of products where each product is a coefficient value multiplied by an integer power of a variable. A polynomial may be specified by a vector of the coefficient values of the polynomial where the vector has a width equal to one plus the degree of the polynomial, the degree of the polynomial being the maximum power of the variable present in the polynomial. Conversely, a vector of arbitrary values may be used to define an associated polynomial. An example polynomial, poly(x)=7x3+6x2+5, has a degree of three and a width of four for the associated vector [7, 6, 0, 5]. For polynomial division over a Galois field, each of the coefficients in the dividend, divisor, quotient, and remainder polynomials are an element from the particular Galois field.
Reed Solomon codes are systematic block codes used for error correction. The input data is partitioned into vectors each containing K symbols. Each vector of input symbols is used to generate a vector containing R check symbols. The combination of K input symbols and R check symbols form an N symbol codeword that may be used to detect and correct corruption of the codeword. The R check symbols correspond to the remainder polynomial from a Galois field polynomial division, where the dividend polynomial is given by the vector of K input symbols and the divisor polynomial is a generator polynomial given by the particular Reed Solomon code that is being used. The generator polynomial has a degree equal to the required number of check symbols minus one.
Evaluating the remainder polynomial from a Galois field polynomial division is a complex operation requiring significant resources such as circuit area and computation time. In an application that continuously generates Reed Solomon encoded data, the evaluation of the remainder polynomial needs to achieve a throughput rate that equals or exceeds the data rate of the vectors of input symbols. Generally, the evaluation of the remainder polynomial is a recursive process requiring K iterations. Each of the iterations requires multiple, simultaneous, Galois field multiplications. The Galois field multiplications are intolerant to the inclusion of pipelining as the additional latency reduces throughput.
While a typical circuit for evaluation of the remainder polynomial for a block code uses a particular generator polynomial having a fixed degree, a flexible circuit for evaluation of the remainder polynomial for a Reed Solomon code uses a generator polynomial having a degree that may be varied. The flexible circuit allows the implementation of various block codes having various numbers of check symbols. The number of check symbols generated by the flexible circuit may even vary in real time by switching the generator polynomial used in real time.
The present invention may address one or more of the above issues.